package binary_sort_tree;

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = { 7, 3, 10, 12, 5, 1, 9 };
        BinarySortTree tree = new BinarySortTree();
        for (int i : arr) {
            tree.add(new Node(i));
        }
        tree.infixOrder();
    }
}

class BinarySortTree {
    Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
}

class Node {
    public int value;
    public Node left;
    public Node right;

    Node(int v) {
        this.value = v;
    }

    // 递归的方式添加，满足二叉排序树的规则
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
                return;
            }
            this.left.add(node);
        } else {
            if (this.right == null) {
                this.right = node;
                return;
            }
            this.right.add(node);
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node [" + this.value + "]";
    }
}